// 回溯法
// 回溯法是一种通过递归来系统地搜索所有可能解的方法。
// 它通过"尝试-撤销"的方式遍历所有选择，适用于组合、排列、子集等问题.


function subsets(nums) {
  const res = []; // 存储所有子集的结果数组

  const backtrack = (start, path) => {
    res.push([...path]); // 记录当前子集（拷贝避免引用问题）

    // 从 start 开始遍历，避免重复子集
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]); // 选择当前数字
      backtrack(i + 1, path); // 递归处理下一个位置
      path.pop(); // 撤销选择（回溯）
    }
  };

  backtrack(0, []); // 从空子集开始回溯
  return res;
}

// 测试
console.log(subsets([1, 2, 3]));
// 输出: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]